﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
//P10446 64位整数乘法 
//typedef long long LL;
//LL a, b, p;
//LL dpow(LL a, LL b, LL p)//倍增思想 
//{
//	LL ret = 0;//LL
//	while (b)
//	{
//		if (b & 1)ret = (ret + a) % p;
//		a = (a + a) % p;
//		b >>= 1;
//	}
//	return ret;
//}
//int main()
//{
//	cin >> a >> b >> p;
//	cout << dpow(a, b, p) << endl;
//	return 0;
}
//P1226 快速幂模板
//typedef long long int LL;
//LL qpow(LL a, LL b, LL p)//需要记忆 快速幂模板
//{
//	LL ret = 1;
//	while (b)
//	{
//		if (b & 1) ret = ret * a % p;
//		a = a * a % p;
//		b >>= 1;
//	}
//	return ret;
//}
//int main()
//{
//	LL a, b, p;
//	cin >> a >> b >> p;
//	printf("%lld^%lld mod %lld=%lld", a, b, p, qpow(a,b,p));
//	return 0;
//}

//取模运算的规则 
//1.计算过程中，当只有加法和乘法时，取模可以放在任意的位置
//（a+b*c+d)%p=(a%p+(b%p)*c+d)%p;
//2.计算过程中，存在减法时，结果可能出现负数，如果需要补正，需要“模加模”
//（a-b)%p=((a-b)%p+p)%p
//3.计算过程中，存在除法时，取模会造成结果错误，需要求逆元
// 
//P2859 牛棚产奶 思路简单 实现略麻烦 还有堆的使用有点忘
//把下一头牛放在最早结束上一次产奶的牛棚里 节省资源
//const int N = 5e4 + 10;
//struct node
//{
//	int index;//下标
//	int home;//使用牛棚编号
//	int a, b;//起始时间与结束时间
//}cow[N];
//struct node2
//{
//	int index;//牛棚编号
//	int t;//结束时间
//	bool operator <(const node2& y) const
//	{
//		return t > y.t;//建小堆用
//	}
//};
//int n;
//bool cmp(node& x, node& y)
//{
//	return x.a < y.a;//根据起始时间 从小到大排序
//}
//bool cmp2(node& x, node& y)
//{
//	return x.index < y.index;//根据下标 从小到大排序 最后输出
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)cow[i].index = i, cin >> cow[i].a >> cow[i].b;
//	sort(cow + 1, cow + 1 + n, cmp);
//	int cnt = 1;
//	priority_queue<node2> heap;//根据t建小堆
//	heap.push({ cnt,cow[1].b });
//	cow[1].home = 1;//先给第一头奶牛安排牛棚
//	for (int i = 2; i <= n; i++)
//	{
//		int tmin = heap.top().t;
//		if (cow[i].a > tmin)//可用当前最早结束的牛棚
//		{
//			cow[i].home = heap.top().index;
//			heap.pop();
//			heap.push({ cow[i].home, cow[i].b });
//		}
//		else//只能另外开一个牛棚
//		{
//			cnt++;
//			cow[i].home = cnt;
//			heap.push({cnt,cow[i].b});
//		}
//	}
//	cout << cnt << endl;
//	sort(cow + 1, cow + 1 + n, cmp2);
//	for (int i = 1; i <= n; i++)
//		cout << cow[i].home << endl;
//	return 0;
//}

//P2887 奶牛防晒霜 贪心区间问题 共有八种排序方式 其中两种能够 结合具体思想 
//阳光值越大的防晒霜优先给耐受力强的的奶牛 对整体影响更小
//const int N = 2510;
//struct node
//{
//	int x;//最小值 //阳光值
//	int y;//最大值 //数量
//}a[N],b[N];
//int n, m;
//bool cmp(node& a, node& b)
//{
//	return a.x > b.x;//左端点从大到小排序 /阳光值从大到小排序
//}
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)cin >> a[i].x >> a[i].y;
//	for (int i = 1; i <= m; i++)cin >> b[i].x >> b[i].y;
//
//	sort(a + 1, a + 1 + n, cmp);
//	sort(b + 1, b + 1 + m, cmp);
//
//	int ret = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		//从大到小给牛分配防晒霜
//		int l = a[i].x, r = a[i].y;
//		for (int j = 1; j <= m; j++)
//		{
//			int w = b[j].x, & cnt = b[j].y;
//			if (cnt == 0)continue;//当前防晒霜用完 取下一个
//			if (w < l) break;//阳光值太小没作用 但已经是最大的了 直接跳出 换头牛
//			if (w > r) continue;//阳光值太大了 选下一个防晒霜
//			//区间刚好 可以分配
//			cnt--;
//			ret++;
//			break;//用完防晒霜了 换头牛
//		}
//	}
//	cout << ret << endl;
//	return 0;
//}
//UVA1193 雷达问题 将二维问题化为一维区间问题 根据左端点排序后 重叠区间连续的特点 进行贪心策略处理
//const int N = 1010;
//struct node
//{
//	double l;
//	double r;
//}a[N];
//bool cmp(node& x, node& y)
//{
//	return x.l < y.l;
//}
//int main()
//{
//	int n, cnt = 0;
//	double d;
//	while (cin >> n >> d, n && d)
//	{
//		cnt++;
//		bool flag = false;
//		for (int i = 1; i <= n; i++)
//		{
//			double x, y; cin >> x >> y;
//			if (y > d)flag = true;
//			double len = sqrt(d * d - y * y);//将每个岛屿的坐标化为一维区间处理
//			a[i].l = x - len; a[i].r = x + len;
//		}
//		cout << "Case " << cnt << ": ";
//		if (flag)cout << "-1" << endl;
//		else
//		{
//			sort(a + 1, a + 1 + n, cmp);//以左端点进行排序 “排序后 相互重叠的区域是连续的”
//			int ret = 1;
//			double r = a[1].r; 
//			for (int i = 2; i <= n; i++)
//			{
//				double right = a[i].r;
//				double left = a[i].l;
//				if (left <= r)//等于也算重叠 雷达能覆盖到
//				{
//					r = min(r, right);//取右端点小的为基准 贪心策略
//				}
//				else
//				{
//					ret++;//没有重叠 取下一段为基准 此处需要布置一个雷达 ret++
//					r = right;
//				}
//			}
//			cout << ret << endl;
//		}
//	}
//	return 0;
//}